package theeg.DependencyAnalysis.Core.Algorithms.CycleDetection;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TarjanCycleDetection {

    private List<List<DependencyNode>> _stronglyConnectedComponents;
    private Stack<DependencyNode> _stack;
    private int _index;

    List<List<DependencyNode>> reportCycles(List<DependencyNode> graph) {
        _stronglyConnectedComponents = new ArrayList();
        _index = 0;
        _stack = new Stack();
        for (DependencyNode v : graph) {
            if (v.cycleIndex < 0) {
                findLinks(v);
            }
        }
        return _stronglyConnectedComponents;
    }

    private void findLinks(DependencyNode v) {
        v.cycleIndex = _index;
        v.lowLink = _index;
        _index++;
        _stack.push(v);

        for (DependencyNode w : v.dependencies) {
            if (w.cycleIndex < 0) {
                findLinks(w);
                v.lowLink = Math.min(v.lowLink, w.lowLink);
            } else if (_stack.contains(w)) {
                v.lowLink = Math.min(v.lowLink, w.cycleIndex);
            }
        }

        if (v.lowLink != v.cycleIndex) {
            return;
        }
        ConvertToNodes(v);
    }

    private void ConvertToNodes(DependencyNode v) {
        List<DependencyNode> scc = new ArrayList();
        DependencyNode x;
        do {
            x = _stack.pop();
            scc.add(x);
        } while (v != x);
        if (scc.size() > 1) {
            _stronglyConnectedComponents.add(scc);
        }
    }
}
